/**
 * 03-树3 Tree Traversals Again
 * 题目的核心是已知前序（压栈的数），中序（出栈的数）遍历的结果来构造二叉树
 * 输出后序遍历的结果
 * 
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 31

typedef struct TreeNode TreeNode;
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

typedef struct Stack Stack;
struct Stack {
    int* data;
    int top;
};

Stack* createStack(int size) {
    Stack *s = (Stack*)malloc(sizeof(Stack));
    s->data = (int*)malloc(sizeof(int)*size);
    s->top = -1;
    return s;
}

void freeStack(Stack *s) {
    free(s->data);
    free(s);
}

void pushStack(Stack* s, int v) {
    s->data[++s->top] = v;
}

int popStack(Stack* s) {
    return s->data[s->top--];
}

// 读取输入参数，返回元素个数，填入先序，中序遍历结果的数组
int read(int* pre, int* in) {
    // 元素个数
    int n;
    scanf("%d", &n);

    Stack* stack = createStack(n);

    // 先序，中序数组下标
    int preIdx=0, inIdx=0;

    for (int i=0; i<2*n; i++) {
        char action[10];
        scanf("%s", action);
        if (strcmp("Push", action) == 0) {
            scanf("%d", &pre[preIdx]);
            pushStack(stack, pre[preIdx]);
            preIdx++;
        } else if (strcmp("Pop", action) == 0) {
            in[inIdx++] = popStack(stack);
        }
    }
    freeStack(stack);
    return n;
}

void printArray(int* a, int n) {
    for (int i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

TreeNode* createTreeNode(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// 前序（压栈的数），中序（出栈的数）遍历的结果来构造二叉树
TreeNode* buildTree(int* pre, int* in, int n) {
    if (n < 1) {
        return NULL;
    }
    TreeNode* root = createTreeNode(pre[0]);
    if (n == 1) {
        return root;
    }
    int rootValue = pre[0];
    int rootInIdx = 0; // 根节点在中序遍历中的位置
    while (rootInIdx < n && in[rootInIdx] != rootValue) {
        rootInIdx++;
    }
    if (rootInIdx >= n) {
        printf("Error");
    }
    int leftLen = rootInIdx; // 左子树长度
    int rightLen = n - leftLen - 1; // 右子树长度
    // printf("n=%d, rootInIdx=%d, leftLen=%d, rightLen=%d\n", n, rootInIdx, leftLen, rightLen);
    root->left = buildTree(pre+1, in, leftLen);
    root->right = buildTree(pre + leftLen + 1, in + rootInIdx + 1, rightLen);
    return root;
}

void PostorderTraversal(TreeNode* root, int* printBlank) {
    if (root == NULL) {
        return;
    }
    PostorderTraversal(root->left, printBlank);
    PostorderTraversal(root->right, printBlank);
    if (*printBlank) {
        printf(" ");
    }
    printf("%d", root->data);
    *printBlank = 1;
}

int main() {
    int in[MAX_SIZE], pre[MAX_SIZE];
    int n;

    n = read(pre, in);
    // printArray(pre, n);
    // printArray(in, n);

    TreeNode* root = buildTree(pre, in, n);
    int pb = 0;
    PostorderTraversal(root, &pb);
    printf("\n");

    return 0;
}